Date modified: Mon 2023-09-18 . 09:01 AM
Date created: Sat 2023-10-07 . 09:02 PM
# Blind coins puzzle. Suppose four coins are arranged at the corners of a square board as follows: ![[1 teaching/summer program 2023/puzzles-and-problems/---files/blind-coins-puzzle 2023-08-06 09.31.47.excalidraw.svg]] %%[[1 teaching/summer program 2023/puzzles-and-problems/---files/blind-coins-puzzle 2023-08-06 09.31.47.excalidraw|🖋 Edit in Excalidraw]], and the [[summer program 2023/puzzles-and-problems/---files/blind-coins-puzzle 2023-08-06 09.31.47.excalidraw.dark.svg|dark exported image]]%% ([interactive coins](https://bonsoon.net/dev/four-coins/)) The coins can be in any configuration of heads facing up, or tails facing up. Your goal is to flip some of them each turn so that the coins are all heads facing up or all tails facing up. If you have successfully done it, a judge will declare "you did it!" However, you must do this **blindfolded**, and you cannot feel the coins to tell whether the head or tail is facing up (so someone could flip for you, or you only hold the edge of the coins). What's worse, each turn after you flip some of them, your **adversary** will rotate the square board at an arbitrary multiple of $90^{\circ}$, **to throw you off**! Can you come up with a strategy to flip the coins so that on some turn, they are all facing the same way (all heads or all tails)? Can you do this in finitely many turns? Can you guarantee a number $N$ such that you can always do this within $N$ steps? Or, can you show this is impossible? Of course, this can be won by just chance, but is there any certainty to it? In summary, we have **The setup:** Four coins arranged in a square. The initial configuration unknown to you. **The goal:** To flip the coins all facing the same way. **Your turn:** You flip some of the coins blindfolded (you can say top left and bottom left, etc). A judge checks if you have done it. If so, you win! Else, your adversary rotates the square board in an arbitrary multiple of $90^{\circ}$. Repeat. Of course this could be won by chance... But we would like some guarantees if possible! ![[---images/---assets/---icons/question-icon.svg]] If the square board is not rotated, what would your strategy be? ![[---images/---assets/---icons/question-icon.svg]] Find a strategy to win, or show that there is no guarantee winning strategy. **Notice, your winning strategy needs to be in a way so that even if your adversary knows your strategy, you will still win.** ![[---images/---assets/---icons/question-icon.svg]] If you found a winning strategy, what is the **least number** $N$ you can guarantee to win within $N$ steps? ![[---images/---assets/---icons/question-icon.svg]] What if instead there are only 3 coins arranged in an **equilateral triangle**? ## Hints. (Some discussed in class.) 1. Remember the goal is to just turn them all heads up or all tails up. 2. Since the board possibly keep rotating, what information is still left after it was being rotated? 3. Notice that when one rotates the board, the number of head or tail coins do not change. 4. How many different TYPES of coin configurations are there? Group together those that are rotationally similar. And by symmetry, the role of heads or tails can be swapped. 5. The winning configuration is the one with all coins heads or tails. 6. How many different TYPES of flipping moves can you do? (Recall each turn you can turn over any number of coins by their location.) 7. How do we related the different types of coin configurations with the different kinds of flipping moves? Draw some arrows to relate them. This gives something called a **directed graph** in mathematics, which is one of the many important objects in math! A graph is just a collection of dots (vertices) and lines (edges) connecting the dots. A directed graph is one where the lines are also arrows with directionality. 8. Come up with a strategy (algorithm / formula / **path on the graph**) to lead to winning configuration, no matter where we start.